package _01_动态数组;

public class _45_跳跃游戏II {

    public static void main(String[] args) {
        _45_跳跃游戏II ii = new _45_跳跃游戏II();
        int[] dps = {0};
        System.out.println(ii.jump(dps));

    }

    // {2, 1}
    // 正向查看元素，看最大前进距离
    public int jump(int[] nums) {
        int len = nums.length - 1;
        int maxPath = 0;
        // 初始跳跃步数
        int step = 0;
        int end = 0;
        for (int i = 0; i < len; i++) {
            // 记录当前走的最元步数
            maxPath = Math.max(maxPath, i + nums[i]);
            if (i == end) {
                end = maxPath;
                step++;
            }
        }
        return step;
    }

    // 正向查找
    public int jump2(int[] nums) {
        int maxPosition = 0;
        int end = 0;
        int step = 0;
        int len = nums.length - 1;
        for (int i = 0; i < len; i++) {
            // 记录当前遍历的最大position
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                step++;
            }
        }
        return step;
    }

    // 反向查找
    public int jump1(int[] nums) {
        // 从后往前推，找到距离其最远能到达的元素
        int position = nums.length - 1;
        int step = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    step++;
                    break;
                }
            }
        }
        return step;
    }

}
